﻿// X-factor Chains POJ - 3421.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>

//https://vjudge.csgrandeur.cn/problem/POJ-3292


using namespace std;

/*
这个问题是基于David Hilbert的 4n + 1 数的理论。

David Hilbert 将比 4 的倍数大 1 的正整数：1、5、9、13、17、21 ...、4n + 1、... 称为 H 数。
这些 H 数组成了一个独立的 H 数空间，我们可以将这些 H 数看作 H 数空间中的唯一数字。 
H 数在乘法下是闭合的，即任意的两个 H 数相乘还是 H 数。

与常规整数一样，我们将 H 数分为成 H 质数和 H 合数，1 既不是 H 质数，也不是 H 合数，我们称它为单位数。
H 质数指的是这个数除了 1 外，只有自身这一个 H 数因子，即如果 H 数 h 除了只能被 1 和 h 自身整除外，
不能被其他 H 数整除，则这个 H 数就是 H 质数。
除 H 质数 和 1 外的其他 H 数都是 H 合数。

例如，前几个 H 合数是：5×5 = 25、5×9 = 45、5×13 = 65、9×9 = 81、5×17 = 85。

你的任务是计算 H-半质数的数量。 H-半质数是 H 数，它恰好是两个 H 质数的乘积，这两个 H 质数可以相同或不同。
在上面的例子中，所有五个数字都是 H-半质数。 125 = 5×5×5 不是 H-半质数，因为它是三个 H 质数的乘积。
Input
每行输入包含一个 H 值 ≤1,000,001。 最后一行输入包含0，程序运行结束。
Output
对于每个输入的 H 数 h，打印一行表示 h 的行和在 1 和 h 之间的H-半质数的数量，以样本中所示的格式分隔一个空格。
Sample Input
21
85
789
0
Sample Output
21 0
85 5
789 62
*/



int main()
{
	

	return 0;
}

 